using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace Gko.Utils
{
	/// <summary>
	/// <see cref="T:Gko.Utils.OrderedEnumerable`1"/> implements a lazy "OrderBy" for <see cref="T:System.Collections.Generic.IEnumerable`1"/>. This class is instantiated by the EnumerableExtensions.LazyOrder* methods.
	/// For more information, see http://code.logos.com/blog/2010/04/a_truly_lazy_orderby_in_linq.html
	/// </summary>
	/// <typeparam name="TSource"></typeparam>
	internal class OrderedEnumerable<TSource> : IOrderedEnumerable<TSource>
	{
		// Creates a new OrderedEnumerable that will sort 'source' according to 'ordering'.
		private readonly IElementComparer<TSource> elementComparer;
		private readonly IEnumerable<TSource> source;

		public OrderedEnumerable(IEnumerable<TSource> source, IElementComparer<TSource> elementComparer)
		{
			this.source = source;
			this.elementComparer = elementComparer;
		}

		#region IOrderedEnumerable<TSource> Members

		/// <summary>
		/// Performs a subsequent ordering on the elements of an <see cref="T:System.Linq.IOrderedEnumerable`1"/> according to a key.
		/// </summary>
		/// <returns>
		/// An <see cref="T:System.Linq.IOrderedEnumerable`1"/> whose elements are sorted according to a key.
		/// </returns>
		/// <param name="keySelector">The <see cref="T:System.Func`2"/> used to extract the key for each element.
		///                 </param><param name="comparer">The <see cref="T:System.Collections.Generic.IComparer`1"/> used to compare keys for placement in the returned sequence.
		///                 </param><param name="descending">true to sort the elements in descending order; false to sort the elements in ascending order.
		///                 </param><typeparam name="TKey">The type of the key produced by <paramref name="keySelector"/>.
		///                 </typeparam><filterpriority>2</filterpriority>
		public IOrderedEnumerable<TSource> CreateOrderedEnumerable<TKey>(Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending)
		{
			var nextComparer = new ElementComparer<TSource, TKey>(keySelector, comparer ?? Comparer<TKey>.Default, descending, null);
			return new OrderedEnumerable<TSource>(this.source, this.elementComparer.Append(nextComparer));
		}

		/// <summary>
		/// Returns an enumerator that iterates through the collection.
		/// </summary>
		/// <returns>
		/// A <see cref="T:System.Collections.Generic.IEnumerator`1"/> that can be used to iterate through the collection.
		/// </returns>
		/// <filterpriority>1</filterpriority>
		public IEnumerator<TSource> GetEnumerator()
		{
			// build an array containing the input sequence
			var array = this.source.ToArray();

			// from the input array, create the sort keys used by each ordering
			this.elementComparer.CreateSortKeys(array);

			// instead of sorting the actual source array, we sort an array of indexes into that sort array; when the
			//   sort is finished, this array (when read in order) gives the indexes of the source array in sorted order
			var sourceIndexes = new int[array.Length];
			for (var i = 0; i < sourceIndexes.Length; i++) {
				sourceIndexes[i] = i;
			}

			// use a random number generator to pick a pivot for partitioning
			var random = new Random();

			// track the index of the item that is next to be returned
			var index = 0;

			// use a stack to simulate the recursive quicksort algorithm iteratively
			var stack = new Stack<Range>();
			stack.Push(new Range(0, array.Length - 1));
			while (stack.Count > 0) {
				// get the range that needs to be sorted
				var currentRange = stack.Pop();

				if (currentRange.Last - currentRange.First <= 8) {
					// if the range is small enough, terminate the recursion and use insertion sort instead
					if (currentRange.First != currentRange.Last) {
						this.InsertionSort(sourceIndexes, currentRange.First, currentRange.Last);
					}

					// yield all the items in this sorted sub-array
					Debug.Assert(currentRange.First == index, "currentRange.First != index");
					while (index <= currentRange.Last) {
						yield return array[sourceIndexes[index]];
						index++;
					}
				} else {
					// recursive case: pick a pivot in the array and partition the array around it
					var pivotIndex = this.Partition(random, sourceIndexes, currentRange.First, currentRange.Last);

					// "recurse" by pushing the ranges that still need to be processed (in reverse order) on to the stack
					stack.Push(new Range(pivotIndex + 1, currentRange.Last));
					stack.Push(new Range(pivotIndex, pivotIndex));
					stack.Push(new Range(currentRange.First, pivotIndex - 1));
				}
			}
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return this.GetEnumerator();
		}

		#endregion

		/// <summary>
		/// Performs a simple insertion sort of the values identified by the indexes in 'sourceIndexes' in the inclusive range [first, last].
		/// Algorithm taken from http://en.wikipedia.org/wiki/Insertion_sort.
		/// </summary>
		/// <param name="sourceIndexes"></param>
		/// <param name="first"></param>
		/// <param name="last"></param>
		private void InsertionSort(int[] sourceIndexes, int first, int last)
		{
			// assume the first item is already sorted, then process all other indexes in the range
			for (var index = first + 1; index <= last; index++) {
				// find the place where value can be inserted into the already sorted elements
				var valueIndex = sourceIndexes[index];
				var insertIndex = index - 1;
				bool done;
				do {
					if (this.elementComparer.Compare(sourceIndexes[insertIndex], valueIndex) > 0) {
						// move the elements to make room
						sourceIndexes[insertIndex + 1] = sourceIndexes[insertIndex];
						insertIndex--;
						done = insertIndex < first;
					} else {
						done = true;
					}
				} while (!done);

				// insert it in the correct location
				sourceIndexes[insertIndex + 1] = valueIndex;
			}
		}

		/// <summary>
		/// Partitions the 'sourceIndexes' array into two halves around a randomly-selected pivot.
		/// Algorithm taken from: http://en.wikipedia.org/wiki/Quicksort
		/// </summary>
		/// <param name="random"></param>
		/// <param name="sourceIndexes"></param>
		/// <param name="first"></param>
		/// <param name="last"></param>
		/// <returns>Returns the index of the pivot in the partitioned array.</returns>
		private int Partition(Random random, int[] sourceIndexes, int first, int last)
		{
			// use random choice to pick the pivot
			var randomPivotIndex = random.Next(first, last + 1);

			// move the pivot to the end of the array
			sourceIndexes.Swap(randomPivotIndex, last);
			var pivotIndex = sourceIndexes[last];

			// process all the items, moving them before/after the pivot
			var storeIndex = first;
			for (var i = first; i < last; i++) {
				if (this.elementComparer.Compare(sourceIndexes[i], pivotIndex) <= 0) {
					sourceIndexes.Swap(i, storeIndex);
					storeIndex++;
				}
			}

			// move the pivot into the "middle" of the array; return its location
			sourceIndexes.Swap(storeIndex, last);
			return storeIndex;
		}

		#region Nested type: Range

		/// <summary>
		/// Range represents an inclusive range of indexes into the array being sorted.
		/// </summary>
		private struct Range
		{
			public Range(int first, int last)
				: this()
			{
				this.First = first;
				this.Last = last;
			}

			public int First
			{
				get;
				private set;
			}

			public int Last
			{
				get;
				private set;
			}
		}

		#endregion
	}
}
